package test230603;

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/3 20:56
 * 978. 最长湍流子数组
 * https://leetcode.cn/problems/longest-turbulent-subarray/
 */
public class Solution03 {

    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int[] f = new int[n];  // f[i], i 位置结尾的子数组且最后处于上升状态的湍流数组最大长度
        int[] g = new int[n];  // g[i], i 位置结尾的子数组且最后处于下降状态的湍流数组最大长度
        // 初始状态, 无论哪种情况, i 位置的子数组的长度至少为 1, 以此也可以减少部分情况的初始化
        Arrays.fill(f, 1);
        Arrays.fill(g, 1);
        // 动态规划迭代过程
        int maxLen = 1;
        for (int i = 1; i < n; ++i) {
            if (arr[i] > arr[i - 1]) {
                // 上升状态
                f[i] = g[i - 1] + 1;
            } else if (arr[i] < arr[i - 1]) {
                // 下降状态
                g[i] = f[i - 1] + 1;
            }
            maxLen = Math.max(maxLen, Math.max(f[i], g[i]));  // 寻求最优解
        }
        return maxLen;
    }
}
